//
// Created by ASUS on 2024/4/18/星期四.
//
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;

int countSubsequences(vector<int>& nums, int k) {
	int n=nums.size();
	vector<vector<ll>> dp(n+1,vector<ll>(k));
	for(int i=1;i<=n;i++){
		dp[i][nums[i-1]%k]+=1;
		for(int j=0;j<k;j++){
			dp[i][(j+nums[i-1])%k]+=dp[i-1][(j+nums[i-1])%k]+dp[i-1][j];
			dp[i][(j+nums[i-1])%k]%=mod;
		}
	}
	return dp[n][0]%mod;
}
//滚动数组优化
int countSubsequences1(vector<int>& nums, int k) {
	int n=nums.size();
	vector<ll> f(k);
	f[nums[0]%k]=1;
	for(int i=1;i<n;i++){
		vector<ll> temp(k);
		temp[nums[i]%k]=1;
		for(int j=0;j<k;j++){
			temp[(j+nums[i])%k]+=f[(j+nums[i])%k]+f[j];
			temp[(j+nums[i])%k]%=mod;
		}
		f=temp;
	}
	return f[0]%mod;
}